Field of the Invention
The present invention is related to the field of computer communications and more particularly to a Content Induced Transaction Overlap (CITO) driver which transmits a block of data.
Description of the Prior Art
Various types of multiple-access channel communication systems are known in the art. These communication systems may conveniently be divided into two distinct types, the Time Division Multiple Access (TDMA) systems, and the Carrier Sensed Multiple Access (CSMA) systems. In Time Division Multiple Access systems as disclosed by Hopkins et al in U.S. Pat. No. 4,161,786; Lowe, Jr. In U.S. Pat. No. 4,199,662 or White et al in U.S. Pat. No. 4,199,661 the transmission channel capacity is divided into time slots during which identified transmitters are allowed to transmit their information over the communication network. Each transmitter is assigned a specific time slot so that each transmitter in turn will have an opportunity to transmit its information. In Carrier Sensed Multiple Access systems, such as disclosed by Eswaran et al in U.S. Pat. No. 4,292,623, Herzog, U.S. Pat. No. 4,199,663, or Spracklen et al in U.S. Pat No. 4,337,465, each transmitter detects when the communication channel is idle, then after a predetermined period of time, attempts to transmit its information. Typically, the waiting period depends on the assigned priority of the transmitter.
The problem with the Time Division Multiple Access system is that often a particular transmitter may not have any information to transmit during its allotted time slot, while other transmitters may generate two or more messages in the period between their allotted time slots. Therefore some transmission time slots are wasted while other messages are delayed while awaiting access to the common transmission line. This problem is partially overcome by the Carrier Sensed Multiple Access system under light or moderate loads. However under high message traffic conditions, the probability of simultaneous access to the common transmission line rises sharply, and excessive amounts of time are wasted resolving priority differences of the involved transmitters. A Content Induced Transaction Overlap Communication System (CITO) as disclosed by Walter et al in U.S. Pat. No. 4,493,074, and assigned to the same assignee as the present invention, is hereby incorporated by reference and is designed to overcome these problems. The present invention is an improvement of the CITO communication channel because the present invention allows the transmission of a block of data of a processor within a bucket in lexicographical order.
A CITO communication system is designed for transmitting data from a plurality of senders to a receiver over a single communication channel. Each sender has a data register which stores the multiple bit data word to be transmitted, a word boundary register which stores the number of bits in the data word and a bit position register. The transmission begins with each sender transmitting the highest order bit stored in the data register. Bits are transmitted on the channel in an overlapped manner such that the channel state is the logical sum or product of the transmitted bits. Using single phase representation, where a zero bit is transmitted as a finite signal level and a one bit is transmitted as a null signal level, the composite channel states are accordingly 0 or 1.
The senders each then compare the state of the communication channel with their transmitted bit to determine if they are the same. If the state of the communication channel is the same as the transmitted bit, the sender transmits its next highest bit and decrements its word boundary and bit position registers. However, if the state of the communication channel is different from its transmitted bit, the sender terminates the transmission of its remaining bits but continues to monitor the communication channel and decrement its word boundary register for each bit transmitted on the communication channel. At the end of the transmission of the data word, indicated by the word boundary register being decremented to zero, each sender enters into bit competition with all of the senders based on the content of its bit position register when it stopped transmitting to determine if it has lexicographically the next smallest data word. If it has, it initiates the sending of its remaining data bits. However, if it doesn't have lexicographically the next smallest data word, the sender waits until the end of the transmission of the current data word and re-enters the bit competition. This cycle repeats until all of the senders have completed the transmission of all the bits in their data words. At this point, all the bit position registers are at zero and no sender performs in the bit competition. The senders recognize the termination of the current data bucket (collection of data bits in the different senders) and the transmission of the next data bucket can begin after sYnchronization.
One of the major advantages of CITO over other communication methods is that it provides for the sorting of data as a by-product of the communication protocol. CITO, however, only provides for the sorting of data in the currently transmitted data bucket. The prior art CITO driver allows each Sender to transmit, at most, a single data item in the data bucket. This restriction severely limits the usefulness of the sorting capability of CITO because each Sender may have many data items. Another advantage of CITO is its data compression capability, however, a transmission method of at most, one data item per data bucket, also reduces the data compression capability. If a Sender has n data items to transmit and no other Senders want to transmit, then the Sender must transmit each data item one by one as a separate independent data bucket. Thus, there is no data compression.
The known solution for providing CITO data compression for a block of data within a single Sender is to incorporate a content addressable memory (CAM) into a CITO driver. If a Sender writes a block of its data into the CAM, the CITO driver can transmit the entire data of the CAM within the same bucket because CAM provides various associative functions such as the calculation of the next minimum value. However, CAM has a high pin/circuit ratio and a high power dissipation. Thus, it is not only expensive, but the fabrication of a large size CAM may not be feasible because of the status of current technology. Also, CITO needs only the one operation, calculation of the next minimum value, not the many associative operations of CAM, therefore, the implementation of CAM for CITO wastes most of CAM's capability.
A variety of other techniques exist for the transmission of data with data reduction. One such technique is a Data Exchange Processor For Distributed Computing System invented by Kober and disclosed in U.S. Pat. No. 4,181,936. This patent describes a distributed computing system which has a data exchange processor that is especially adapted to control operations involving the transfer of data among components of the distributed computing system. This system differs from the present invention because the distributed computing system does not provide for the transmission of distributed messages in lexicographical order. U.S. Pat. No. 4,698,628 by Herkert et al, discloses A Method And Apparatus For Transmission Of Data With Data Reduction. In this patent the data which is transmitted between the several network levels is reduced by deleting data which corresponds to a predetermined information content. This disclosure differs from the present invention because this disclosure does not provide for the transmission of distributed messages in lexicographical order. U.S. Pat. No. 4,598,411 issued to Berkovich et al and assigned to the same assignee as the present invention is hereby incorporated by reference and discloses an On-The-Fly Data Compression System. This system compresses the data transmitted between the data source and ultimate utilization device. The data compression modules compress the data using a word representation by associative processing buffer and a content induced transaction overlap (CITO) transmission protocol which results in an interleaved transmission of data bits and bit position bits, the latter being indicative of the number of data bits that will be transmitted during the subsequent data transmission. This disclosure, however, differs from the present invention because it does not provide for the transmission of a block of data of a Sender within a data bucket in lexicographical order.